# -*- coding: utf-8 -*-

''' 
Autores: 
Pedro Godinho - 6355
Pedro Lopes - 9850
'''

import sys
import math
from random import uniform
import time
import matplotlib.pyplot as plt

''' Class responsable for SelectionSort algorithm and tests'''
class SelectionSort:

    '''@param A: list to sort'''
    def selectionsort (self,A):
            n=len(A)
            for i in range(n-1):
                    mini = i
     
                    for j in range(i+1,n):
                            if(A[j]<A[mini]):
                                    mini=j
     
                    A[i],A[mini]=A[mini],A[i]

    def grafico(self):
        Z = [1] + range(50, 1050, 50)
        T = []
        M = 50
        for n in Z:
            A = [ uniform(0.00,1.0) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = time.time()
                self.selectionsort(A)
                t2 = time.time()
                tempos.append(t2-t1)
            media = reduce(lambda x, y: x + y, tempos) / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]
        ct=12e6
        Z = [n**2/ct for n, media, var in T]


        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X, Z, 'b^', label=u"previsão teórica")
        plt.title("Selection Sort")
        plt.legend()
        plt.show()
